package main

import "fmt"

func combinationSum(candidates []int, target int) [][]int {
	sum := 0
	track := []int{}
	res := [][]int{}
	backtracking(sum, 0, target, candidates, track, &res)
	return res
}

//回溯
func backtracking(sum, now_i, target int, candidates, track []int, res *[][]int) {
	fmt.Println(sum, now_i, track, target)
	if sum == target {
		a := make([]int, len(track))
		copy(a, track)
		*res = append(*res, a)
		return
	}
	if sum > target {
		return
	}
	n := len(candidates)
	for i := now_i; i < n; i++ {
		sum += candidates[i]
		if sum > target {
			continue
		}
		track = append(track, candidates[i])
		backtracking(sum, i, target, candidates, track, res)
		track = track[:len(track)-1]
		sum -= candidates[i]
	}
}

func main() {
	candidates := []int{2, 3, 6, 7}
	target := 7
	res := combinationSum(candidates, target)
	fmt.Println(res)
}
